import java.util.ArrayList;
import java.util.List;

public class LeetCode22 {
    public static void main(String[] args) {
        int n = 8;

        System.out.println(generateParenthesis(n));
    }

    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        dfs(0, n * 2, 0, n, "", ans);
        return ans;
    }

    /**
     * i: 当前遍历到位置
     * n: 字符总长度
     * score: 当前得分，令 '(' 为 1， ')' 为 -1
     * max: 最大得分值
     * path: 当前的拼接结果
     * ans: 最终结果集
     */
    static void dfs(int i, int n, int score, int max, String path, List<String> ans) {
        if (i == n) {
            if (score == 0) ans.add(path);
        } else {
            // 如果添加左括号后不超过 max（有效值），则可以添加
            if (score + 1 <= max) {
                dfs(i + 1, n, score + 1, max, path + "(", ans);
            }

            // 如果添加右括号后不少于 0（有效值），则可以添加
            if (score - 1 >= 0) {
                dfs(i + 1, n, score - 1, max, path + ")", ans);
            }
        }
    }
}
